package offer;

import jdk.nashorn.internal.objects.annotations.Function;

/**
 * @Author Elephas
 * @Date 2022/1/29
 **/
@FunctionalInterface
public interface IsMatch {
    boolean isMatch(String s,String patten);
}

/**
 * 未考虑嵌套，测试用例含嵌套情况
 */

class IsMatchImpl1 implements IsMatch{

    @Override
    @Deprecated
    public boolean isMatch(String s, String patten) {
        char[] charS = s.toCharArray();
        char[] charPatten = (patten + "#").toCharArray();
        int ptrS = 0,ptrPatten = 0;
        boolean isMatch = true;
        while(ptrS < charS.length && ptrPatten < charPatten.length){
            if(charPatten[ptrPatten] != '*') {
                if (charPatten[ptrPatten] == '.') {
                    ptrPatten++;
                    ptrS++;
                } else {
                    if (charS[ptrS] == charPatten[ptrPatten]) {
                        ptrPatten++;
                        ptrS++;
                    } else {
                        isMatch = false;
                        break;
                    }
                }
            }else{
                break;
            }
        }
        if(!isMatch) {
            return false;
        }else{
            return true;
        }
    }
}

/**
 * 题目理解有问题，X* 表示匹配多个X，而非匹配 X 后再匹配任意字符
 */
class IsMatchImpl2 implements IsMatch{
    static final String TEST_01_S = "aab";
    static final String TEST_01_PATTEN = "c*a*b";

    static final String TEST_02_S = "ab";
    static final String TEST_02_PATTEN = ".*";

    static final String TEST_03_S = "ab";
    static final String TEST_03_PATTEN = ".*c";

    static final String TEST_04_S = "aaa";
    static final String TEST_04_PATTEN = "a*a";
    public static void main(String[] args) {
        new IsMatchImpl3().isMatch(TEST_04_S,TEST_04_PATTEN);
    }

    @Override
    public boolean isMatch(String s, String patten) {
        char[] charS = (s+"#").toCharArray();
        char[] charPatten = (patten + "#").toCharArray();
        int ptrS = 0,ptrPatten = 0;
        boolean isMatch = true;
        while(ptrS < charS.length && ptrPatten < charPatten.length){
            if(charS[ptrS] == charPatten[ptrPatten] || charPatten[ptrPatten] == '.'){
                ptrPatten++;
                ptrS++;
            }else if( charPatten[ptrPatten] == '*'){
                // condition that charPatten[ptrPatten] == '*'
                ptrPatten++;
                while (ptrS < charS.length && charS[ptrS] != charPatten[ptrPatten]){
                    ptrS++;
                }
                if(charS[ptrS] != charPatten[ptrPatten]){
                    isMatch = false;
                    break;
                }
            }else if(charS[ptrS] != charPatten[ptrPatten]){
                isMatch = false;
                break;
            }
        }
        return isMatch;
    }
}

class IsMatchImpl3 implements IsMatch{

    @Override
    public boolean isMatch(String s, String patten) {
        char[] charS = (s+"#").toCharArray();
        char[] charPatten = (patten + "#").toCharArray();
        int ptrS = 0,ptrPatten = 0;
        boolean isMatch = true;
        while(ptrS < charS.length && ptrPatten < charPatten.length){
            if((ptrPatten + 1) < charPatten.length && charPatten[ptrPatten + 1] == '*'){
                if(charPatten[ptrPatten] == '.'){
                    ptrPatten++;
                    ptrPatten++;
                    while(charS[ptrS] != '#' && charS[ptrS] != charPatten[ptrPatten]){
                        ptrS++;
                    }
                }else{
                    if(charPatten[ptrPatten] != charPatten[ptrPatten + 2]) {
                        while (charS[ptrS] == charPatten[ptrPatten]) {
                            ptrS++;
                        }
                        ptrPatten += 2;
                    }else{
                        while (charS[ptrS] == charPatten[ptrPatten]) {
                            ptrS++;
                        }
                        ptrPatten += 3;
                    }
                }

            }else {
                if (charS[ptrS] == charPatten[ptrPatten] || charPatten[ptrPatten] == '.') {
                    ptrPatten++;
                    ptrS++;
                } else if (charS[ptrS] != charPatten[ptrPatten]) {
                    isMatch = false;
                    break;
                }
            }
        }
        return isMatch;
    }
}